package com.company.test24;

import com.sun.xml.internal.ws.policy.privateutil.PolicyUtils;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by Administrator on 2016.10.19.
 */
public class SortLargeFile {
    public static final int MAX_ARRAY_SIZE=100000;

    public static void main(String[] args) throws IOException{
        sort("src/largedata.dat","src/newData");
    }

    //给该分段大文件排序，输入目标大文件
    public static void sort(String sourcefile,String targetfile)throws IOException{
        String f1="f1.dat";
        String f2="f2.dat";
        String f3="f3.dat";
        int segmentSize=MAX_ARRAY_SIZE;

        int numberOfSegments=initializeSegments(MAX_ARRAY_SIZE,sourcefile,f1);
        while (segmentSize>1){
            DataInputStream f1Input=new DataInputStream(
                    new BufferedInputStream(new FileInputStream(f1)));

            DataOutputStream f2Output=new DataOutputStream(
                    new BufferedOutputStream(new FileOutputStream(f2)));
            copyHalfSegments(numberOfSegments,segmentSize,f1Input,f2Output);

            DataInputStream f2Input=new DataInputStream(
                    new BufferedInputStream(new FileInputStream(f2)));

            DataOutputStream f3Output=new DataOutputStream(
                    new BufferedOutputStream(new FileOutputStream(f3)));

            mergerSegments(numberOfSegments,segmentSize,f1Input,f2Input,f3Output);

            numberOfSegments=(int)Math.ceil(1.0*numberOfSegments/2);
            segmentSize=segmentSize*2;

            File file1=new File(f1);
            File file2=new File(f2);
            File file3=new File(f3);
            file1.delete();
            file2.delete();
            file3.renameTo(new File("f1.dat"));
        }

        File file=new File(f1);
        file.renameTo(new File(targetfile));
    }

    //归并所有分段
    private static void mergerSegments(int numberOfSegments,
                                       int segmentSize, DataInputStream f1,
                                       DataInputStream f2, DataOutputStream f3)throws IOException{

        for(int i=0;i<numberOfSegments/2;i++){
            mergeTwoSegments(segmentSize,f1,f2,f3);
        }

        while (f1.available()>0){
            f3.writeInt(f1.readInt());
        }

        f1.close();
        f2.close();
        f3.close();
    }

    //复制前半边的分段
    private static void copyHalfSegments (int numberOfSegments,int segmentSize,
                                         DataInputStream f1,DataOutputStream f2)throws IOException{
        //System.out.println(f1.available());
        //System.out.println(numberOfSegments);
        //System.out.println(segmentSize);
        for(int i=0;i<numberOfSegments/2*segmentSize;i++){
            f2.writeInt(f1.readInt());
        }
        f2.close();
    }

    //给单独一个文件创造有序分段，并返回其分段的值
    private static int initializeSegments(int segmentSize,String originalFile,String f1)throws IOException {
        DataInputStream input=new DataInputStream(
                new BufferedInputStream(new FileInputStream(originalFile)));
        DataOutputStream output=new DataOutputStream(
                new BufferedOutputStream(new FileOutputStream(f1)));

        int numberOfSegments=0;
        while (input.available()>0){
            numberOfSegments++;
            int[] arrayList=new int[segmentSize];

            int i=0;
            for(;i<segmentSize&&input.available()>0;i++){
                arrayList[i]=input.readInt();
            }
            Arrays.sort(arrayList,0,i);
            for(int j=0;j<i;j++){
                output.writeInt(arrayList[j]);
            }
        }
        input.close();
        output.close();
        return numberOfSegments;
    }

    //归并两个分段
    private static void mergeTwoSegments(int segmentSize,DataInputStream f1,
                                         DataInputStream f2, DataOutputStream f3)throws IOException{
        int intFromF1=f1.readInt();
        int intFromeF2=f2.readInt();
        int f1Count=1;
        int f2Count=1;

        while (true){
            if(intFromF1<intFromeF2){
                f3.writeInt(intFromF1);
                if(f1.available()<=0||f1Count++>=segmentSize){
                    f3.writeInt(intFromeF2);
                    break;
                }else {
                    intFromF1=f1.readInt();
                }
            }else{
                f3.writeInt(intFromeF2);
                if(f2.available()<=0||f2Count++>=segmentSize){
                    f3.writeInt(intFromF1);
                    break;
                }else {
                    intFromeF2=f2.readInt();
                }
            }
        }

        while (f1.available()>0&&f1Count<segmentSize){
            f3.writeInt(f1.readInt());
            f1Count++;
        }

        while (f2.available()>0&&f2Count<segmentSize){
            f3.writeInt(f2.readInt());
            f2Count++;
        }
    }
}
